package com.base.dynamicprograming;

import java.util.*;

/**
 * TODO
 *
 * @author leon
 * @date 2021年12月06日 19:38
 */
public class WordBreak {

    public boolean wordBreak(String s, List<String> wordDict) {
        if(s == null||s.length()==0){
            return false;
        }
        Set<String> set = new HashSet<>(wordDict);

        int n = s.length();
        boolean[] dp = new boolean[n+1];
        dp[0] = true;
        for (int end = 1; end < n+1; end++) {
            // dp[i] 表示字符串 s 前 i 个字符组成的字符串 s[0..i) 是否能被空格拆分成若干个字典中出现的单词
            // 判断从0 到 end{[0,end)左开右闭},判断当前位置end(不包括end)
            for (int i = 0; i < end; i++) {
                if(dp[i]&&set.contains(s.substring(i,end))){
                    dp[end] = true;
                    break;
                }
            }

        }

        return dp[n];
    }

    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<>();
        list.add("leet");
        list.add("code");
        new WordBreak().wordBreak("leetcode",list);
    }
}
